package com.lyj.sc.dynamicProgramming.test20220720;

/**
 * @program: code-random
 * @description:
 * @author: lyj
 * @create: 2022-07-20 16:06
 * @version: 1.0
 * @Modifier By:
 **/
public class Solution {
    // 518.  零钱兑换 II
    public int change(int amount, int[] coins) {
        //完全背包问题
        int [] dp = new int[amount+1];
        //抽成0的组合数为1
        dp[0]=1;
        int size = coins.length;
        //先物品在背包
        for (int i = 0; i < coins.length; i++) {
            for(int k = coins[i];k<=amount;k++){
                dp[k]+=dp[k-coins[i]]+1;
            }
        }
        return dp[amount];
    }
    // 416. 分割等和子集
    public boolean canPartition(int[] nums) {
        //求和
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        //背包
        int bagsize = sum/2;
        //1.定义数组
        int[]dp = new int[bagsize+1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = bagsize; j > nums[i]; j--) {
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return sum==2*dp[bagsize];
    }
    // 1049. 最后一块石头的重量 II  和分割等和子集一样 分割成两堆石头
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for (int stone : stones) {
            sum+=stone;
        }
        //背包问题
        int bagsize = sum/2;
        //1.定义数组
        int [] dp = new int[bagsize+1];
        for (int i = stones.length; i > 0; i--) {
            for (int j = bagsize; j >=stones[i]; j--) {
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[bagsize]*2;
    }
}
